package leetcode.tree_problem;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class 从前序与中序遍历序列构造二叉树 {
    public int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return buildHelp(preorder , inorder , 0 , preorder.length - 1);
    }
    public TreeNode buildHelp (int[] preOrder, int[] inOrder , int left , int right){
        //方法的语义很重要：根据pre、in，left、right确定树
        if (left > right){
            return null;
        }
        if (index == preOrder.length){
            return null;
        }
        TreeNode root = new TreeNode(preOrder[index]);
        index ++;
        //现在已经确定了树根per也处理了第一个元素，下面在inorder中找到这个值的索引位置确定这个树的左子树；
        //注意这个方法的语义以所给条件确定树（根）；
        //下面分别处理左右子树部分
        int pos = findIndex(inOrder , root);//找到root在inOrder中的索引
        root.left = buildHelp(preOrder , inOrder , left , pos - 1);//他的左子树在他根的左面，所有左子树都在左面
        root.right = buildHelp(preOrder , inOrder , pos + 1 , right);//右子树
        return root;
    }
    public int findIndex(int[] inOrder , TreeNode root){
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == root.val){
                return i;
            }
        }
        return -1;
    }
}
